package problem912;

//912.排序数组
//https://leetcode.cn/problems/sort-an-array/

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    public void quickSort(int[] nums, int left, int right) {
        if(left >= right) return;
        int index = partSort(nums, left, right);
        quickSort(nums, left, index-1);
        quickSort(nums, index+1, right);
    }
    public int middleNum(int[] nums, int left, int right) {
        int mid = left + (right-left)/2;
        int key = mid;
        if(nums[left] < nums[right]) {
            if(nums[mid] < nums[left]) key = left;
            else if(nums[mid] < nums[right]) key = mid;
            else key = right;
        }else {
            if(nums[mid] < right)  key = right;
            else if(nums[mid] < left) key = mid;
            else key = left;
        }
        swap(nums, left, key);
        return left;
    }
    public int partSort(int[] nums, int left, int right) {
        // 三数取中
        int key = middleNum(nums, left, right);
        while(left < right) {
            //右边找比key小的数
            while(left < right && nums[right] >= nums[key]) {
                right--;
            }
            //左边找比key大的数
            while(left < right && nums[left] <= nums[key]) {
                left++;
            }
            //交换
            swap(nums, left, right);
        }
        swap(nums, key, left);
        return left;
    }
    public void  swap(int[] nums, int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}